In this video we compare time complexity of different operations on different datastructures and deduce the importance of Binary Search Tree.
This track of the course covers the topic "BST".
In details, this track will cover:
Objective: The objective of this track is to familiarize the learners with BSTs.
Track Content:
Assessment: All Tracks in every week are associated with weekly contests.
In this video we compare time complexity of different operations on different datastructures and deduce the importance of Binary Search Tree.
In this video we take a brief introduction about Binary Search Trees.Also we briefly discuss about different operations on Binary Search Trees.
In this video we discuss about search operation in Binary Serach Tree. The basic idea is that we end up with a leaf note if the key is not present in the BST.
In this video we discuss two methods (recursive and iterative) to implement a function in C++ that takes root and key as parameters and return True if the key is present in the BST and returns False if the key is not present in BST.
Codes:
In this video we discuss two methods (recursive and iterative) to implement a function in Java that takes root and key as parameters and return True if the key is present in the BST and returns False if the key is not present in BST.
Codes:
In this video we learn how to insert a node in a BST, the basic idea is that we first search for the key and if the key is not present in the BST then we insert the key with the leaf node. Else if the key is already present in the BST then we do nothing.
In this video we discuss two methods(recursive and iterative) to insert to a node in a Binary Search Tree in C++.
Codes:
In this video we discuss two methods(recursive and iterative) to insert a node in a BST in Java.
Codes:
In this video we discuss how to delete a node from a Binary Search There are three posibilities:
1.Node to be deleted is a leaf node.
2.Node to be deleted has only one child.
3.Node to be deleted has two children.
we also learn, inorder successor is the closest higher value and inorder predecessor is the closest lower value.
This video discusses the concept of Floor in Binary Search Tree along with the discussion on time complexity.
This video deals with the concept of the floor in Binary Search Tree and its implementation in C++.
Code:
This video deals with the concept of the floor in Binary Search Tree and its implementation in Java.
Code:
This video deals with the concept and working of the ceiling of a key in Binary Search Tree.
Codes:
This video discusses the working of a Self Balancing Binary Search Tree.
This video discusses the AVL tree. This is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
This video discusses the Red-Black Tree. This is a self-balancing Binary Search Tree (BST) where every node follows the following rules:
This video discusses the various applications of a binary search tree.
This video introduces us to Set in the C++ STL class. It also shows the implementation of the set through examples and explains few functions associated with the Set STL class in C++.
Codes:
This video introduces us to Map in the C++ STL class. It also shows the implementation of the set through examples and explains few functions associated with the Map STL class in C++.
Codes:
This video explains Tree Set In Java and the various operations involved with it.
Codes:
This video explains TreeMap In Java and the various operations involved with it.
Codes:
This video discusses the problem of accepting an array and for every element of the array, one needs to find the Ceiling on Left Side.
Codes:
This video discusses the problem of finding the Kth Smallest Binary Search Tree.
Codes:
This video discusses the problem of checking whether a binary tree is a binary search tree or not.
Codes:
Given a binary search tree with two swapped nodes, the task is to fix the binary search tree by swapping them back.
Codes:
The problem discusses finding the pair of the sum in given Binary Search Tree.
Codes:
Given a binary tree, we need to find sum of nodes in all vertical lines starting from leftmost line to rightmost.
Codes:
Given a binary tree, we need to print nodes in all vertical lines starting from leftmost line to rightmost.
Codes:
A Vertical Traversal based approach is discussed in this video
Codes:
A solution using Vertical Traversal is discussed in the video
Codes:

Searching a Key
Using the property of Binary Search Tree, we can search for an element in O(h) time complexity where h is the height of the given BST.
Step 1: Compare 6 with 8.
Since 6 is less than 8,
move to left subtree.
Step 2: Compare 6 with 3.
Since 6 is greater than 3,
move to its right subtree.
Step 3: Comapre 6 with 6.
Node Found.
Insertion of a Key
Inserting a new node in the Binary Search Tree is always done at the leaf nodes to maintain the order of nodes in the Tree. The idea is to start searching the given node to be inserted from the root node till we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.100 100
/ \ Insert 40 / \
20 500 ---------> 20 500
/ \ / \
10 30 10 30
\
40
20 30 40 50 60 70 80

Element to be inserted: 2
Step 1: Compare 2 with 8.
Since 2 is less than 8,
move to left subtree.
Step 2: Compare 2 with 3.
Since 2 is less than 3,
move to its left subtree.
Step 3: Comapre 2 with 1.
Since 2 is greater than 1 and also 1 is a leaf node.
Insert 2 as its right child of node 1.
Inorder traversal of the given tree
20 30 40 50 60 70 80
Delete 20
Inorder traversal of the modified tree
30 40 50 60 70 80
Delete 30
Inorder traversal of the modified tree
40 50 60 70 80
Delete 50
Inorder traversal of the modified tree
40 60 70 80



LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20
The LCA or Lowest Common Ancestor of any two nodes N1 and N2 is defined as the common ancestor of both the nodes which is closest to them. That is the distance of the common ancestor from the nodes N1 and N2 should be least possible.
LCA of 10 and 14 is 12
LCA of 14 and 8 is 8
LCA of 10 and 22 is 20


Why AVL Trees?
Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn) for all these operations. The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree.Insertion
To make sure that the given tree remains AVL after every insertion, we must augment the standard BST insert operation to perform some re-balancing. Following are two basic operations that can be performed to re-balance a BST without violating the BST property (keys(left) < key(root) < keys(right)).T1, T2 and T3 are subtrees of the tree
rooted with y (on the left side) or x (on
the right side)
Keys in both of the above trees follow the
following order:
keys(T1) < key(x) < keys(T2) < key(y) < keys(T3)
So BST property is not violated anywhere.
T1, T2, T3 and T4 are subtrees.
Asked In: Linkedin
Asked In: Microsoft
Asked In: Amazon
Asked In: VMWare
Asked In: Samsung
A | O(n) for all |
B | O(Logn) for all |
C | O(Logn) for search and insert, and O(n) for delete |
D | O(Logn) for search, and O(n) for insert and delete |